Search results for "Karp–Lipton theorem"
showing 3 items of 3 documents
Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms
2005
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory
2007
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponenti…
Quantum Query Complexity of Boolean Functions with Small On-Sets
2008
The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = |{x|f(x) = 1}| or the size of f's on-set. We prove that: (i) For $poly(N)\le M\le 2^{N^d}$ for some constant 0 < d < 1, the upper bound of Q(f) is $O(\sqrt{N\log M / \log N})$. This bound is tight, namely there is a Boolean function f such that $Q(f) = \Omega(\sqrt{N\log M / \log N})$. (ii) For the same range of M, the (also tight) lower bound of Q(f) is $\Omega(\sqrt{N})$. (iii) The average value of Q(f) is bounded from above and below by $Q(f) = O(\log M +\sqrt{N})$ and $Q(f) = \Omega (\log M/\log N+ \sqrt{N…